//剑指 Offer 25. 合并两个排序的链表

#include <stdlib.h>

struct ListNode {
	int val;
	struct ListNode* next;
};
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
	if (!l1)
		return l2;
	if (!l2)
		return l1;

	struct ListNode* head = NULL, * tail = NULL;
	while (l1 && l2)
	{
		//尾插
		if (l1->val < l2->val)
		{
			//尾插时要注意是否为第一次插入
			if (NULL == tail)//第一次插入
			{
				head = tail = l1;
			}
			else//非第一次插入
			{
				tail->next = l1;
				tail = tail->next;
			}
			l1 = l1->next;
		}
		else
		{
			if (NULL == tail)
			{
				head = tail = l2;
			}
			else
			{
				tail->next = l2;
				tail = tail->next;
			}
			l2 = l2->next;
		}
	}

	if (!l1)
		tail->next = l2;
	else
		tail->next = l1;
	
	return head;
}